#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 79.单词搜索
// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
// 如果 word 存在于网格中，返回 true ；否则，返回 false 。

class Solution {
private:
    int d[4][2] = {{-1, 0}, {0,1},{1,0},{0,-1}};    // 偏移量数组：顺时针的4个方向
    int m,n;    //平面board的size
    vector<vector<bool>> visited;   // 记录二位数组是否被访问过

    bool inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    // 从board[startx][starty]开始，寻找word[index...word.size())
    bool searchWord(const vector<vector<char>> &board, const string &word, int index, int startx, int starty) {
        if(index == word.size() - 1)    // 到了最后一个字符
            return board[startx][starty] == word[index];

        if(startx == 0 && starty == 2)
            cout<<"haha\n";
        // 考察当前的字符和board上的字符是否相等
        if(board[startx][starty] == word[index]) {
            visited[starty][starty] = true;
            cout<<"set visited["<<startx<<"]["<<starty<<"] = true"<<endl;
            cout<<"match board["<<startx<<","<<starty<<"] = "<<board[startx][starty]<<", word["<<index<<"] = "<<word[index]<<endl;
            if(index == 3)
                cout<<"index==3"<<endl;
            if(visited[2][2] == true)
                cout<<"visited[2][2] == true"<<endl;
            // 从startx，starty出发，向四个方向寻找
            for(int i = 0; i < 4; i++) {
                int newx = startx + d[i][0];    // 计算新的坐标
                int newy = starty + d[i][1];
                if(newx == 2 && newy == 2)
                    cout<<"newx == 2 && newy == 2"<<endl;
                // 确保新坐标没有越界，且没有被访问过，且找到了index+1后面的所有元素
                if(inArea(newx,newy) && !visited[newx][newy]) {
                    bool searchbool = searchWord(board, word, index+1, newx, newy);
                    if(searchbool)
                        return true;
                }
            }
            cout<<"set visited["<<startx<<"]["<<starty<<"] = false"<<endl;
            visited[startx][starty] = false;    // 不再占有这个位置
        }
        // 当前字符不相等
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        assert(m > 0);  // 二维平面至少有一行
        n = board[0].size();
        assert(n > 0);
        // 访问的数组的初始化。这部分和视频讲解的不一样
        visited.clear();
        visited = vector<vector<bool>>(m, vector<bool>(n, false));
//        for(int i = 0; i < m; i++)
//            visited.emplace_back(vector<bool>(n, false));

        // 遍历一遍二维数组。每一重都尝试从(i,j)出发来寻找word
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[i].size(); j++)
                if(searchWord(board,word,0,i,j))
                    return true;
        return false;
    }
};

int main() {
    char b1[3][4] = {{'A', 'B', 'C', 'E'},
                     {'S', 'F', 'C', 'S'},
                     {'A', 'D', 'E', 'E'}};
    vector<vector<char>> board1;
    for( int i = 0 ; i < 3 ; i ++ )
        board1.push_back(vector<char>(b1[i], b1[i] + sizeof(b1[i]) / sizeof(char)));

    int cases = 3;
    string words[3] = {"ABCCED", "SEE", "ABCB" };

    Solution().exist(board1,string("ABCCED"));
//    for(int i = 0 ; i < cases ; i ++)
//        if(Solution().exist(board1,words[i]))
//            cout << "found " << words[i] << endl;
//        else
//            cout << "can not found " << words[i] << endl;
    return 0;
}
